package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/5/8 8:44
 */
public class C1723 {

    // 将数组分成 k个子序列
    // 使其最大值最小
    public static int minimumTimeRequired(int[] jobs, int k) {
        int[] help = new int[k];
        return process(jobs, 0, help, k);
    }

    public static int process(int[] nums, int i, int[] help, int k) {
        if (i == nums.length) {
            int ans = -1;
            for (int j = 0; j < k; j++) {
                ans = Math.max(ans, help[j]);
            }
            return ans;
        } else {
            int ans = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                help[j] += nums[i];
                ans = Math.min(ans, process(nums, i + 1, help, k));
                help[j] -= nums[i];
            }
            return ans;
        }
    }

    public static int minimumTimeRequired2(int[] jobs, int k) {
        int[] help = new int[k];
        return process2(jobs, 0, help, k);
    }

    public static int process2(int[] nums, int i, int[] help, int k) {
        if (i == nums.length) {
            int ans = -1;
            for (int j = 0; j < k; j++) {
                ans = Math.max(ans, help[j]);
            }
            return ans;
        } else {
            int ans = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                help[j] += nums[i];
                ans = Math.min(ans, process2(nums, i + 1, help, k));
                help[j] -= nums[i];
            }
            return ans;
        }
    }


    // for test
    public static void main(String[] args) {
        int[] jobs = {3, 2, 3};
        int k = 3;
        System.out.println(minimumTimeRequired(jobs, k));
    }

}
